package LC;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.com/problems/triangle/description/
 * Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
 * For example, given the following triangle
 * [
 * [2],
 * [3,4],
 * [6,5,7],
 * [4,1,8,3]
 * ]
 * The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
 * Note:
 * Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
 */
public class LC_120_Triangle_Path_Greedy_DP {
    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(Arrays.asList(2));
        triangle.add(Arrays.asList(3, 4));
        triangle.add(Arrays.asList(6, 5, 7));
        triangle.add(Arrays.asList(4, 1, 8, 3));
        int n = Solution.minimumTotal(triangle);
        System.out.println(n);
    }

    static class Solution {
        static int minimumTotal(List<List<Integer>> triangle) {
            int row = triangle.size();
            if (row == 0) return 0;
            int[][] res = new int[row][row];
            int minSum = Integer.MAX_VALUE;
            List<Integer> list0 = triangle.get(0);
            if (list0.size() == 0)
                return 0;
            if (row == 1)
                return list0.get(0);
            res[0][0] = list0.get(0);
            for (int i = 1; i < row; i++) {
                List<Integer> list = triangle.get(i);
                for (int j = 0; j < list.size(); j++) {
                    if (j == 0) {
                        res[i][j] = res[i - 1][j] + list.get(j);
                    } else if (j == list.size() - 1) {
                        res[i][j] = res[i - 1][j - 1] + list.get(j);
                    } else {
                        res[i][j] = Math.min(res[i - 1][j - 1], res[i - 1][j]) + list.get(j);
                    }
                    if (i == row - 1) {
                        minSum = Math.min(res[i][j], minSum);
                    }
                }
            }
            return minSum;
        }
    }
}